\documentclass[12pt]{article}
\usepackage{amsfonts,amssymb}
\usepackage{amsmath}
\usepackage{graphicx}

%\documentstyle[12pt,amsfonts]{article}
%\documentstyle{article}

\setlength{\topmargin}{-.5in}
\setlength{\oddsidemargin}{0 in}
\setlength{\evensidemargin}{0 in}
\setlength{\textwidth}{6.5truein}
\setlength{\textheight}{8.5truein}
%
%\input ../adgeomcs/lamacb.tex
\input mac.tex
\input mathmac.tex
%
\input xy
\xyoption{all}

\def\fseq#1#2{(#1_{#2})_{#2\geq 1}}
\def\fsseq#1#2#3{(#1_{#3(#2)})_{#2\geq 1}}
\def\qleq{\sqsubseteq}

%
\begin{document}
\begin{center}
\fbox{{\Large\bf Spring, 2009 \hspace*{0.4cm} CIS 511}}\\
\vspace{1cm}
{\Large\bf Introduction to the Theory of Computation\\
Homework 1\\}
\vspace{0.5cm}
\textbf{Jian Chang, Sanjian Chen, Yeming Fang}\\
\vspace{0.2cm}
\itshape{\{jianchan,sanjian,yeming\}@cis.upenn.edu}

\end{center}



``A problems'' are for practice only, and should not
be turned in.

\medskip\noindent
{\bf Problem A1.}
Given an alphabet $\Sigma$, prove
that the relation $\leq_1$ over $\Sigma^*$ defined such that
$u \leq_1 v$ iff $u$ is a prefix of $v$, is a partial ordering.
Prove that the relation $\leq_2$ over $\Sigma^*$ defined such that
$u \leq_2 v$ iff $u$ is a substring of $v$, is a partial ordering.

\medskip\noindent
{\bf Solution A1.} Need to prove that $\leq_1$ and
$\leq_2$ are reflexive, transitive and antisymmetric.

\medskip\noindent
{\bf Problem A2.}
Given an alphabet $\Sigma$, for any language $L\subseteq \Sigma^*$,
prove that $L^{**} = L^*$ and $L^*L^* = L^*$.

\medskip\noindent
{\bf Solution A2.}
$$ L^* = \bigcup_{n \geq 1} L^n $$
$$ L^** = ( \bigcup_{n \geq 1} L^n)^* = \bigcup_{n \geq 1} \{L^n\}^* $$
$$= \bigcup \{L^1 \}^* \cdots \{L^n \}^* = \bigcup \{L^1 \cdots L^n \} \cdots \{L^n \cdots L^{n^2} \} = \bigcup_{n \geq 1} L^n = L^* $$

\vspace {0.5cm}\noindent
{\bf Problem A3.}
Let $D = (Q,\Sigma,\delta,q_0,F)$ be a DFA.
Prove that for all $p\in Q$ and all $u, v\in \Sigma^*$,
\[
\delta^*(p, uv) = \delta^*(\delta^*(p, u), v).
\]

\medskip\noindent
{\bf Solution A3.} Assume that $ \delta^*(p, uv) = r $ and $
\delta^*(p, u) = q $, therefore $ \delta^*(q, v) = r $. Then we
have:
$$ \delta^*(\delta^*(p, u), v) = \delta^*(q, v) = r = \delta^*(p, uv)$$

\vspace {0.5cm}
``B problems'' must be turned in.

\vspace {0.25cm}\noindent {\bf Problem B1 (30 pts).} Let $D =
(Q,\Sigma,\delta,q_0,F)$ be a DFA. Recall that a state $p\in Q$ is
{\it accessible\/} or {\it reachable\/} iff there is some string
$w\in\Sigma^*$, such that
$$\delta^{*}(q_0,w) = p,$$
i.e., there is some path from $q_0$ to $p$ in $D$. Consider the
following method for computing the set $Q_{r}$ of reachable states
(of $D$): define the sequence of sets $Q_{r}^{i}\subseteq Q$, where

\medskip
$Q_{r}^{0} = \{q_0\}$,

\medskip
$Q_{r}^{i+1} = \{q\in Q \mid \exists p\in Q_{r}^{i}, \exists a\in\Sigma,\>
q = \delta(p,a)\}$.

\medskip
(i) Prove by induction on $i$ that $Q_{r}^{i}$ is the set of
all states reachable from $q_0$ using paths of length $i$
(where $i$ counts the number of edges).

\medskip
Show that there may not be any $i_0$  such that
$Q_{r}^{i_{0}+1} = Q_{r}^{i_{0}}$,  by giving
a counter-example.

\medskip
(ii) Show that there may not be any $i_0$  such that
$Q_{r}^{i_{0}} = Q_{r}$,
by giving a counter-example.

\medskip
(iii) Change the inductive definition of $Q^i_r$ as follows:
$$Q_{r}^{i+1} = Q^i_r\cup
\{q\in Q \mid \exists p\in Q_{r}^{i}, \exists a\in\Sigma,\>
q = \delta(p,a)\}.$$
Prove that there is a smallest integer $i_0$ such that
$$Q_{r}^{i_{0}+1} = Q_{r}^{i_{0}} = Q_{r}.$$

Define the DFA $D_r$ as follows:
$D_r = (Q_r,\Sigma,\delta_r,q_0,F\cap Q_r)$,
where $\mapdef{\delta_r}{Q_r\times\Sigma}{Q_r}$
is the restriction of $\delta$ to $Q_r$.
Explain why $D_r$ is indeed a DFA, and
prove that $L(D_r) = L(D)$.
A DFA is said to be {\it reachable, or trim\/}, if
$D = D_r$.

\vspace {0.25cm}\noindent
{\bf Solution B1.}

$Q_r^{n+1}= \{q\in Q \mid \exists p\in Q_r^n, \exists
a\in\Sigma,q=\delta(p,a)\}.$


\vspace {0.25cm}\noindent
(i) Proof:
\begin{enumerate}
 \item When $ i = 0$, the only string with length 0 is $\epsilon$. And, $\delta(q_0,\epsilon)=q_o$. Therefore,  $Q_{r}^{0} = \{q_0\}$, and $Q_{r}^{0}$ is the set of all states reachable from $q_0$ using paths of length $0$.
 \item When $ i = n$, assume that $Q_{r}^{n}$ is the set of all states reachable from $q_0$ using paths of length $n$. That is to say, given any string $w\in\Sigma^*$ of length $n$. There exists a state $q\in Q_{r}^{n}$, such that $\delta^*(p,w)=q$.
 \item When $i=n+1$, given any string $w\in\Sigma^*$ of length $n+1$, there exits string $w'$ of length $n$ $(w\in\Sigma^*)$ and symbol $a\in\Sigma$, such that $w=w^,a$. By induction hypothesis, there exists a state $q\in Q_{r}^{n}$, such that $\delta^*(p,w')=q$. According to the definition, $Q_{r}^{n+1} = \{q\in Q \mid \exists p\in Q_{r}^{n}, \exists a\in\Sigma,\> q = \delta(p,a)\}$. Then we can have that $Q_{r}^{n+1}$ is the set of all states reachable from $q_0$ using paths of length $n+1$.
\end{enumerate}
In conclusion, $Q_{r}^{i}$ is the set of all states reachable from $q_0$ using paths of length $i$.

\vspace {0.25cm}\noindent
(ii) The following DFA should serve as counter-examples for both cases:
$$D = (Q,\Sigma,\delta,q_0,F), Q=\{S_1,S_2\}, \Sigma=\{a\}, q_0=S_1, F=\{S_2\}$$
$$
\xymatrix{ S_1 \ar[r]^{a}  & \> S_2 \ar[l]^{a} \\}
$$

\vspace {0.25cm}\noindent
(iii) Assume there does not exist such a smallest integer $i_0$. Then, according to the definition, for any $i>0$, $Q_{r}^{i+1} - Q_{r}^{i} \neq \emptyset$, and $Q_{r}^{i} \subseteq Q_{r}^{i+1}$. Therefore, when $i\rightarrow\infty$, the number of states in $Q_{r} \rightarrow\infty $. Then, it contradicts with the definition of DFA.

\vspace {0.25cm}\noindent
$D_r$ is indeed a DFA, since it says :``Define the DFA $D_r \cdots $". Besides, the five-tuple of $D_r$ comply with the definition of DFA.

\vspace {0.25cm}\noindent
\begin{enumerate}
    \item $(F \cap Q_r) \subseteq F$, it is trivial to show that $L(D_r) \subseteq L(D)$.
    \item Given any string $w \in L(D)$, according to definition, $p = \delta^*(q_0,w) \in F$. Following the path of symbols in string $w$, $p$ is reachable, \textit{i.e.}, $p \in Q_r$. Therefore, we can have $p \in (F \cap Q_r)$. We now have $L(D) \subseteq L(D_r)$.
\end{enumerate}
With (1)(2), we have $L(D) = L(D_r)$.

\vspace{0.25cm}
\noindent
{\bf Problem B2 (20 pts).}
Given a string $w$, its reversal
$w^R$ is defined inductively as follows:
$\epsilon^R = \epsilon$ and $(ua)^R = au^R$,
where $a\in \Sigma$ and $u\in\Sigma^*$.
Prove that $(uv)^R = v^Ru^R$.
Prove  that $(w^R)^R = w$.

\vspace {0.25cm}\noindent
{\bf Solution B2.}

\vspace {0.25cm}\noindent
(i) Proof:
Assume string $w=uv$, the length of string $u$ is $j$, the length of string $v$ is $i$. Therefore, the length of string $w$ is $i+j$.

\begin{enumerate}
 \item When $i = 0$, $v=\epsilon$. $(uv)^R = (u\epsilon)^R = (u)^R$. According to the definition, $\epsilon^R = \epsilon$, $v^R u^R=\epsilon^R u^R=\epsilon u^R = u^R$. Therefore, $(uv)^R=v^R u^R$.

 \item When $i = 1$, $v=a$. $(uv)^R = (ua)^R $. According to the definition, $(ua)^R = a^R u^R = v^R u^R$. Therefore, $(uv)^R=v^R u^R$.

 \item When $i = n$, assume that $(uv)^R=v^R u^R$.

 \item When $i=n+1$, $v=av'$, and the length of $v'=n$. $(uv)^R = (uav')^R$. Using induction hypothesis and definition, $(uav')^R = v'^R(ua)^R = v'^Rau^R = (v'a)^Ru^R = v^Ru^R$.

\end{enumerate}
With (1)(2)(3)(4), we have $(uv)^R=v^R u^R$.

\vspace {0.25cm}\noindent
(ii) Proof:
Assume the length of string $w$ is $i$.

\begin{enumerate}
 \item When $i = 0$, $w=\epsilon$. According to the definition, $(\epsilon^R)^R = (\epsilon)^R = \epsilon$. Therefore, $(w^R)^R = w$.

 \item When $i = 1$, $w=a$. $(a^R)^R = (a)^R = a$. Therefore, $(w^R)^R = w$.

 \item When $i = n$, assume that $(w^R)^R = w$.

 \item When $i=n+1$, $w=aw'$, and the length of $w'=n$. $(w^R)^R = ((aw')^R)^R = (w'^Ra)^R = a(w'^R)^R$. Using induction hypothesis, $a(w'^R)^R = aw' = w$.

\end{enumerate}
With above, we have $(w^R)^R = w$.

\vspace {0.25cm}
\noindent
{\bf Problem B3 (30 pts).}
Given any alphabet $\Sigma$, prove the following
property: for any two strings $u, v\in\Sigma^*$, $uv = vu$ iff
there is some $w\in\Sigma^*$ such that $u = w^m$ and $v = w^n$, for
some $m, n\geq 0$.


\vspace {0.25cm}\noindent
{\bf Solution B3.}

\vspace {0.25cm}\noindent
Proof:
\begin{itemize}
    \item $\Leftarrow$ When $u = w^m$ and $v = w^n$, for some $m, n\geq 0$, then $uv=w^{m+n}=vu $
    \item $\Rightarrow$ When $uv=vu$
    \begin{itemize}
        \item If $ length(u) = length(v) $, then exits $w=v=u$ and $m=n=1$.
        \item Else, we define operation $O(u,v)=\hat{w}$. Given two stings $u,v$, $length(u)=i$, $length(v)=j$, $i>j$, and $i=kj+r (k \in N, r<j)$, then $\hat{w}$ is the last $r$ symbols in u.
            \begin{itemize}
                \item If $v=(\hat{w})^{n'}$, then $u=(\hat{w})^{kn'+1}$, we have $w=\hat{w}, n=n', m=kn'+1$.
                \item Else, continue to perform operation $O(v,\hat{w})$ on the shorter string $v$ and $\hat{w}$, and so on, until $length(O(v,\hat{w}))=1$.
                \item We acclaim that it must have $v=(\hat{w})^{n'}$ in some steps shown above. If not, then it contradicts with the precondition $uv=vu$.
            \end{itemize}
    \end{itemize}
    \item With $\Leftarrow$ and $\Rightarrow$, we show that for any two strings $u, v\in\Sigma^*$, $uv = vu$ iff there is some $w\in\Sigma^*$ such that $u = w^m$ and $v = w^n$, for some $m, n\geq 0$.
\end{itemize}

\vspace{0.25cm}
\noindent
{\bf Problem B4 (50 pts).}
Given any two DFA's
$D_1 = (Q_1, \Sigma, \delta_1, q_{0, 1}, F_1)$
and \\
$D_2 = (Q_2, \Sigma$, $\delta_2, q_{0, 2}, F_2)$,
a {\it morphism $\mapdef{h}{D_1}{D_2}$ of DFA's\/} is a function
$\mapdef{h}{Q_1}{Q_2}$ satisfying the following two conditions:

\begin{enumerate}
\item[(1)]
$h(\delta_1(p, a)) = \delta_2(h(p), a)$,
for all $p\in Q_1$ and all $a\in \Sigma$;
\item[(2)]
$h(q_{0, 1}) = q_{0, 2}$.
\end{enumerate}

An {\it $F$-map $\mapdef{h}{D_1}{D_2}$ of DFA's\/} is a morphism
satisfying the condition
\begin{enumerate}
\item[(3a)]
$h(F_1) \subseteq F_2$.
\end{enumerate}

\medskip
An {\it $F^{-1}$-map $\mapdef{h}{D_1}{D_2}$ of DFA's\/} is a morphism
satisfying the condition
\begin{enumerate}
\item[(3b)]
$h^{-1}(F_2) \subseteq F_1$.
\end{enumerate}

\medskip
A {\it proper homomorphism of DFA's\/} is an $F$-map
of DFA's which is also an $F^{-1}$-map of DFA's, i.e.
it satisfies the condition
\begin{enumerate}
\item[(3c)]
$h^{-1}(F_2) = F_1$.
\end{enumerate}

\medskip
We say that a morphism (resp. $F$-map, resp. $F^{-1}$-map)
$\mapdef{h}{D_1}{D_2}$  is
{\it surjective\/} if $h(Q_1) = Q_2$.

\medskip
(a)
Prove that
if $\mapdef{f}{D_1}{D_2}$ and $\mapdef{g}{D_2}{D_3}$ are
morphisms (resp. $F$-maps, resp $F^{-1}$-maps) of DFAs,
then $\mapdef{g\circ f}{D_1}{D_3}$ is also a morphism
(resp. $F$-map, resp $F^{-1}$-map) of DFAs.

\medskip
Prove that if  $\mapdef{f}{D_1}{D_2}$ is an $F$-map that is
an isomorphism then it is also an $F^{-1}$-map, and that
if  $\mapdef{f}{D_1}{D_2}$ is an $F^{-1}$-map that is
an isomorphism then it is also an $F$-map.


\medskip
(b)
If $\mapdef{h}{D_1}{D_2}$  is a morphism
of DFA's, prove that
$$h(\delta_1^*(p, w)) = \delta_2^*(h(p), w),$$
for all $p\in Q_1$ and all $w\in \Sigma^*$.

\medskip
As a consequence, prove the following facts:

\medskip
If $\mapdef{h}{D_1}{D_2}$  is an $F$-map of DFA's, then
$L(D_1) \subseteq L(D_2)$.
If $\mapdef{h}{D_1}{D_2}$  is an $F^{-1}$-map of DFA's, then
$L(D_2) \subseteq L(D_1)$.
Finally, if $\mapdef{h}{D_1}{D_2}$  is a proper  homomorphism of DFA's, then
$L(D_1) = L(D_2)$.

\medskip
(c)
Let $D_1$ and $D_2$ be DFA's and assume that there is a
morphism   $\mapdef{h}{D_1}{D_2}$.
Prove that $h$ induces a unique surjective morphism
$\mapdef{h_r}{(D_1)_r}{(D_2)_r}$
(where $(D_1)_r$ and $(D_2)_r$ are the trim DFA's
defined in problem B1). This means that
if   $\mapdef{h}{D_1}{D_2}$ and   $\mapdef{h'}{D_1}{D_2}$
are DFA morphisms, then $h(p) = h'(p)$ for all
$p\in (D_1)_r$,
and the restriction of $h$ to $(D_1)_r$ is surjective onto $(D_2)_r$.
Moreover, if $L(D_1) = L(D_2)$,
prove that $h$ induces a unique surjective
proper  homomorphism   $\mapdef{h_r}{(D_1)_r}{(D_2)_r}$.

\medskip
(d)
Relax the condition that a DFA morphism
$\mapdef{h}{D_1}{D_2}$ maps $q_{0, 1}$ to $q_{0, 2}$
(so, it is possible that $h(q_{0, 1})\not= q_{0, 2}$), and call
such a function a {\it weak morphism\/}.
We have an obvious notion of {\it weak $F$-map\/},
{\it weak $F^{-1}$-map\/} and {\it weak proper
homomorphism\/}
(by imposing condition (3a) or
condition (3b), or (3c)).
For any language, $L \subseteq \Sigma^*$ and any fixed
string, $u\in \Sigma^*$, let $D_u(L)$, also denoted
$L/u$ (called the  {\it (left) derivative of $L$ by $u$\/}), be
the language
\[
D_u(L) = \{v\in \Sigma^*\mid uv \in L\}.
\]
Prove the following facts,
{\bf assuming that $D_2$ is trim}:
If $\mapdef{h}{D_1}{D_2}$  is a weak $F$-map of DFA's, then
$L(D_1) \subseteq D_u(L(D_2))$,
for some suitable $u\in\Sigma^*$.
If $\mapdef{h}{D_1}{D_2}$  is a weak $F^{-1}$-map of DFA's, then
$D_u(L(D_2)) \subseteq L(D_1)$,
for the same $u$ as above.
Finally, if $\mapdef{h}{D_1}{D_2}$  is a weak proper
homomorphism of DFA's, then
$L(D_1) = D_u(L(D_2))$,
for the same $u$ as above.

\medskip
Suppose there is a weak morphism
$\mapdef{h}{D_1}{D_2}$. What can you say about
the restriction of $h$ to $(D_1)_r$?
What can you say about surjectivity ?
(you may need
to consider $(D_2)_r$ with respect to a {\bf different}
start state). What happens (and what can you say)
if $D_2$ is {\bf not} trim?

\vspace{0.25cm}
\noindent
{\bf Solution B4.}

\vspace{0.25cm}
\noindent
(a)(i) Proof:
\begin{itemize}
    \item Since $f(F_1) \subseteq F_2$, and $g(F_2) \subseteq F_3$, $g \circ f(F_1)=g(f(F1)) \subseteq F_3$.
    \item Similarly, $f^{-1}(F_2) \subseteq F_1$, and $g^{-1}(F_3) \subseteq F_2$, ${g \circ f}^{-1}(F_3)=f^{-1}(g^{-1}(F3)) \subseteq F_1$.
\end{itemize}
According to the definition of homomorphism of DFA's, $\mapdef{g\circ f}{D_1}{D_3}$ is also a morphism.

\vspace{0.25cm}
\noindent
(a)(ii) Proof: For any function $\mapdef{f}{X}{Y}$ and any two subsets $A \subseteq X$ and $B \subseteq Y$,\newline
\begin{center}
$ f(A) \subseteq B$ iff $f^{-1}(B) \subseteq A$.

\end{center}
\begin{itemize}
    \item If $\mapdef{f}{D_1}{D_2}$ is an $F$-map, that is $f(F_1) \subseteq F_2$, then we have $f^{-1}(F_2) \subseteq F_1$. According to the definition, it is also an $F^{-1}$-map.
    \item Similarly, if $\mapdef{f}{D_1}{D_2}$ is an $F^{-1}$-map, that is $f(F_2) \subseteq F_1$, then we have $f^{-1}(F_1) \subseteq F_2$. According to the definition, it is also an $F$-map.
\end{itemize}

\vspace{0.25cm}
\noindent
(b) Proof:
Assume the length of string $w$ is $i$.
\begin{enumerate}
 \item When $i = 1$, $w=a$. According to the definition, $h(\delta_1^*(p, w)) = h(\delta_1(p, a)) = \delta_2(h(p),a) = \delta_2^*(h(p),a) = \delta_2^*(h(p),w)$.

 \item When $i = n$, assume that $h(\delta_1^*(p, w)) = \delta_2^*(h(p),w)$.

 \item When $i=n+1$, $w=aw'$, and the length of string $w'$ is $n$. Then we have:
    $$h(\delta_1^*(p, w)) = h(\delta_1^*(p, aw')) = h( \delta_1^*(\delta_1^*(p, a), w'))$$
    Using induction hypothesis:
  $$h( \delta_1^*(\delta_1^*(p, a), w')) = \delta_2^*(h(\delta_1^*(p, a)),w') = \delta_2^*(\delta_2(h(p),a),w') = \delta_2^*(h(p),aw') = \delta_2^*(h(p),w)$$
\end{enumerate}
With (1)(2)(3), we have $h(\delta_1^*(p, w)) = \delta_2^*(h(p),w)$.

\vspace{0.25cm}
\noindent
As a consequence,
\begin{itemize}
    \item For all strings $w$, which $\delta_1^*(q_{0,1},w) \subseteq F_1 $. Since $\mapdef{h}{D_1}{D_2}$  is an $F$-map of DFA's, then $h(\delta_1^*(q_{0,1},w)) = \delta_2^*(h(q_{0,1}),w) = \delta_2^*(q_{0,2},w) \subseteq F_2$. Then we have $L(D_1) \subseteq L(D_2)$.
    \item Similarly, for all strings $w$, which $ \delta_2^*(q_{0,1},w) \subseteq F_2 $. Since $\mapdef{h}{D_1}{D_2}$  is an $F^{-1}$-map of DFA's, then $h(\delta_2^*(q_{0,2},w)) = \delta_1^*(h(q_{0,2}),w) = \delta_1^*(q_{0,1},w) \subseteq F_1$. Then we have $L(D_2) \subseteq L(D_1)$.
    \item For proper homomorphism of DFA's, with above, it is trivial to show that $L(D_1) = L(D_2)$.
\end{itemize}

\vspace{0.25cm} \noindent
 (c) Proof:
\begin{enumerate}
  \item Unique: We firstly prove that, if $\exists p\in (D_1)_r$ so that $h(p)\neq
  h'(p)$, then we can find $q,p\in (D_1)_r$ so that
  $\delta_1(q,a)=p$, where $a\in \Sigma$, $h(q)=h'(q)$ and $h(p)\neq
  h'(p)$. By definition of morphism, we have
  $h(p_{0,1})=h'(p_{0,1}) = p_{0,2}$.
  \vspace{.25cm}

  Suppose $p\in (D_1)_r$ so that $h(p)\neq h'(p)$, since all
  elements $\in (D_1)_r,(D_2)_r$ are reachable from
  $p_{0,1},p_{0,2}$, there must be two different paths from
  $p_{0,2}$ to $h(p)$ and $h'(p)$. Denote the last state $\in
  (D_2)_r$ where the two paths meet as $h(q)=h'(q)$, then the next
  states are $h(p)\neq h'(p)$. Here $p,q\in (D_1)_r$ are the states
  meeting the above requirements.
  \vspace{0.25cm}

  From the definition of morphism we have $h(p)=\delta_2(h(q),a)$
  and $h'(p)=\delta_2(h'(q),a)$. Since $h(q)=h'(q)$, so we have
  $h'(p)=\delta_2(h(q),a)$. Since $h(p)\neq h'(p)$, this means
  $\delta_2(h(q),a)$ has two different values, which contradicts the
  deterministic property of DFA. So $\forall p\in (D_1)_r, h(p) =
  h'(p)$.
  \item Surjective: Suppose surjective property is not met, that is
  $\exists x\in (D_2)_r$ so that $\forall p\in (D_1)_r, h(p)\neq x.$
  By definition of morphism we have $h(p_{0,1})=p_{0,2}$, so we can
  find $y,x\in (D_2)_r$ that, $\exists q\in (D_1)_r$ that $h(q)=y$
  but $\forall p\in (D_1)_r$ that $h(p)\neq x$.
  \vspace{0.25cm}

  Since $D_2$ is DFA, suppose $a\in \Sigma$ that $\delta_2(y,a)=x$.
  Denote $p\in (D_1)_r$ so that $p=\delta_1(q,a)$, then $h(p)\neq
  x$. By the definition of morphism, $\exists z\in (D_2)_r$ so that
  $z=h(p)$. Since $h(\delta_1(q,a))=\delta_2(h(q),a)$, so that
  $h(p)=\delta_2(y,a)=z$. Here we have $\delta_2(y,a)=x=z$, but
  $x\neq h(p)=z, x\neq z$, this means $\delta_2(y,a)$ has two values, which contradicts with the deterministic property
  of DFA. So $\mapdef{h}{D_1}{D_2}$ is surjective.

  \item Homomorphism: We firstly prove that $\forall f_1\in (F_1)_r,
  \exists f_2\in (F_2)_r$ so that $h(f_1)=f_2$. Suppose not, then
  $\exists p_2\in (D_2)_r$ while $p_2$ not $\in (F_2)_r$ that
  $h(f_1)=p_2$.
  \vspace{0.25cm}

  Denote $w\in \Sigma^*$ that $\delta_1^*(p_{0,1},w)=f_1$. Since
  $h(p_{0,1})=p_{0,2}$ and $h(f_1)=p_2$, so that
  $\delta_2^*(p_{0,2},w)=p_2$. Due to the deterministic property of
  $D_2$, $\delta_2^*(p_{0,2},w)$ has only one value $p_2$. Since
  $p_2$ not $\in (F_2)_r$, so $w$ not $\in L(D_2)$. This contradicts
  with $L(D_1)=L(D_2)$.
  \vspace{0.25cm}

  In the same way, $\forall f_2\in (D_2)_r, \exists f_1\in (D_1)_r$
  that $h(f_1)=f_2$. In sum, we have $h^{-1}((F_2)_r)=(F_1)_r$. So
  $h$ induces a proper homomorphism $\mapdef{h'}{(D_1)_r}{(D_2)_r}$.
  Note that $h'$ is also unique and surjective from the proof above.
\end{enumerate}
(d) Proof:
\begin{enumerate}
  \item When $h$ is a weak $F-map$, denote $p\in D_2=h(q_{0,1})$,
  and $u$ is a string over $\Sigma$ that $\delta_2^*(q_{0,2},u)=p$.
  $\forall w\in L(D_1)$, since h is a weak $F-map$, we have
  $\delta_2^*(p,w)\in F_2$, and then $\delta_2^*(q_{0,2},uw)\in
  F_2$. So $uw\in L(D_2), w\in D_u(L(D_2))$. That is $\forall w\in
  D(L_1), w\in D_u(L(D_2))$. So we have $L(D_1)\subseteq D_u(L(D_2))$.

  \item When $h$ is a weak $F^{-1}-map$, denote $p\in D_2=h(q_{0,1})$,
  and $u$ is a string over $\Sigma$ that $\delta_2^*(q_{0,2},u)=p$.
  $\forall uw\in L(D_2))$, since h is a weak $F^{-1}-map$, we have
  $h^{-1}(\delta_2^*(q_{0,2},uw))=\delta_1^*(q_{0,1},w)$, so that
  $w\in L(D_1)$. Since $w\in D_u(L(D_2))$, that is $\forall w\in
  D_u(L(D_2))$, $w\in L(D_1))$. So we have $D_u(L(D_2))\subseteq
  L(D_1)$.

  \item $\forall w\in L(D_1)$, by definition of homomorphism and the
  analysis above, we have $\delta_2^*(q_{0,2},uw)\in F_2$, that is
  $uw\in L(D_2))$, so $w\in D_u(L(D_2))$.

  $\forall uw\in L(D_2)$, in the same way, we have
  $\delta_1^*(q_{0,1},w)\in F_1$, that is $w\in L(D_1)$. In sum, we
  have $L(D_1)=D_u(L(D_2))$.

  \item If $h$ is a weak morphism, $h$ may not be unique from
  $(D_1)_r$ to $D_2$. This can be shown when $D_2$ contains some
  unreachable state groups, each of which is the same as $(D_1)_r$.
  In such situation, $(D_1)_r$ can match any such group, making $h$
  not unique.

  If $h(q_{0,1})\neq q_{0,2}$, then $h$ is not surjective. The
  states in $D_2$ which are previous to $h(q_{0,1})$ don't have
  matching states in $D_1$.

  Further, when $D_2$ is not trim, h is not unique and not surjective.
\end{enumerate}

 {\bf Problem B5 (40 pts).} (a) For any language $L\subseteq
\{a\}^*$, prove that if $L = L^*$, then there is a finite language
$S\subseteq L$ such that $L = S^*$. Prove that $L$ is regular.

\medskip
(b) Let  $L\subseteq \{a\}^*$ be any infinite regular language.
Prove that there is a finite set $F\subseteq \{a\}^*$,
and some strings $a^m$, $a^{p_1}, \ldots, a^{p_k}$,
and $a^q\not=\epsilon$, with
$0\leq p_1 < p_2 < \ldots < p_k < q$, such that
$$L = F\cup \bigcup_{i = 1}^k
a^{m + p_i}\{a^q\}^*.$$

\vspace{0.25cm} \noindent
\noindent
{\bf Solution B5}

\vspace{0.25cm} \noindent
(a)(i) Proof:
If $L = \{\epsilon\}$, it is easy to show $S = \{\epsilon\}$, $S \subseteq L$, and $L = S^*$.
Else,
\begin{itemize}
	\item Firstly, let $\epsilon \in S$. Assume $L$ contains $n+1$ strings $(n\geq0)$, namely: $L=\{\epsilon, a^{m_1}, \cdots , a^{m_n}\}$, and $(m_1 \leq m_2 \leq \cdots \leq m_n)$. Then we can classify each string $a^m \in L$ into one of the ${m_1}$ congruence classes, according to the remainder of $m/m_1$. If the $ith$ congruence class is not empty, then let the string $a^{m_i}$, which ${m_i}$ is the smallest number in the ith congruence class, belongs to $S$. According to this construction of $S$, we can see $S$ is a finite set. For any string $a^m \in L$, assume $a^m$ belongs to the $ith$ congruence class, it is trivial to show that there exists $p \in Z$, $a^m = a^{m_i+p*m_1}$. That is to say, $L \subseteq S^*$.
	\item Since $S \subseteq L$, then $S^* \subseteq L^* = L$. We have $S^* \subseteq L$.
\end{itemize}
With above, we complete the proof.

\vspace{0.25cm} \noindent
(a)(ii) Proof:
\begin{enumerate}
	\item It is easy to construct a set of NFA $N_s$ to accept each string in $S$.
	\item Add a new start state, a new final state, and necessary transition with $\epsilon$. It is easy to combine all the NFA in $N_s$, and get a single NFA $N_S$, with its language equals to $S$.
	\item Add transition with $\epsilon$ from the new final state to the new start state, then we have the NFA $N_{S^*}$, with its language equals to $S^*$.
	\item Convert the NFA $N_{S^*}$ to DFA.
\end{enumerate}
Following the steps above, we have a DFA with its language equals to $L$, then $L$ is regular.

\vspace{0.25cm} \noindent
(b) Proof: If $L$ is a regular language, then it can be accepted by a
certain DFA, denoted as $D$. Since $\Sigma=\{a\}$ with the
deterministic property of DFA, there can only be one circle in $D$,
and its general state is showed in Figure \ref{fig_B5}. Suppose we have $m$
states before the circle with $q$ states. Let $F$ be the set of
final states in first m states. Further more, if $jth$ state in the
circle is final, then there is $p_i=j$. Suppose there are $k$ final
states in the circle, so we have $k$ values of $p_i(1\leq i\leq k)$.
Since each circle represents $q$ a's in a string, so $\{a^q\}^*$ can
represent any number of circles in a string. Here
$\bigcup_{i=1}^ka^{m+p_i}$ can represent the final states in the
circle. Together with set $F$, we can have
$L=F\cup\bigcup_{i=1}^ka^{m+p_i}\{a^q\}^*$.
 \vspace {0.25cm}\noindent
\begin{center}
\begin{figure}
  % Requires \usepackage{graphicx}
  \includegraphics[width=0.9\linewidth]{fig}
  \caption{DFA:$D$}\label{fig_B5}
\end{figure}
\end{center}

 {\bf Problem B6
(50 pts).} (a) Given any two DFA's $D_1$ and $D_2$, prove that there
is a DFA $D$ and two  DFA $F^{-1}$-maps $\mapdef{\pi_1}{D}{D_1}$ and
$\mapdef{\pi_2}{D}{D_2}$ such that the following {\it universal
mapping property of products\/} holds:
For any DFA $M$ and any two DFA $F^{-1}$-maps \\
$\mapdef{f}{M}{D_1}$ and $\mapdef{g}{M}{D_2}$, there is
a {\it unique\/} DFA $F^{-1}$-map $\mapdef{h}{M}{D}$ such that
\[f = \pi_1\circ h
\quad\hbox{and}\quad
g = \pi_2\circ h,\]
as shown in the diagram below:
%\[\matrice{
%                       &                     &               D_1        \cr
%             & \mapdiagul{f}        & \mapupr{\pi_1}          \cr
%M            & \maprightu{h}                  &  D                    \cr
%             & \mapdiagdr{g}        & \mapdownr{\pi_2}                    \cr
%                       &                     &               D_2        \cr
%}\]
\[
\xymatrix{
  &   \> D_1 \\
M     \ar[ru]^{f} \ar[r]^{h} \ar[rd]_{g} &
  D   \ar[u]_-{\pi_1}    \ar[d]^-{\pi_2}      \\
  &  \> D_2
}
\]
Moreover, prove that $\pi_1$ and $\pi_2$ are surjective.
Prove that $D$ is unique up to a DFA $F^{-1}$-map isomorphism.
This means that if $D'$ is another DFA and if there are two
DFA $F^{-1}$-maps $\mapdef{\pi_1'}{D'}{D_1}$
and $\mapdef{\pi_2'}{D'}{D_2}$ such that
the universal mapping property of products holds, then
there are two unique DFA $F^{-1}$-maps $\mapdef{\varphi}{D}{D'}$ and
$\mapdef{\varphi'}{D'}{D}$ so that
$\varphi'\circ \varphi = \id_{D}$,
$\pi_1 = \pi_1'\circ  \varphi$, $\pi_2 =  \pi_2'\circ \varphi$,
$\varphi\circ \varphi' = \id_{D'}$,
$\pi_1' = \pi_1\circ  \varphi'$ and $\pi_2' =  \pi_2\circ \varphi'$.
What is the language accepted by $D$?

\remark
We call $D$ the {\it product of $D_1$ and $D_2$\/}
and we denote it by $D_1\prod D_2$.

\medskip
(b)
Given any three DFA's $D_1$, $D_2$, and $D_3$
and any two DFA $F^{-1}$-maps
$\mapdef{f}{D_1}{D_3}$ and $\mapdef{g}{D_2}{D_3}$,
prove that there is a DFA
$D$ and two  DFA $F^{-1}$-maps $\mapdef{\pi_1}{D}{D_1}$
and $\mapdef{\pi_2}{D}{D_2}$ such that
\[f\circ \pi_1 = g\circ \pi_2,\]
as in the diagram below
%\[
%\matrice{
%D            &  \maprightu{\pi_1}  &  D_1          \cr
%\mapdownl{\pi_2}   &                 & \mapdownr{f}\cr
%D_2            & \maprightd{g}&  D_3,            \cr
%}
%\]
%
\[
\xymatrix{
D \ar[r]^{\pi_1} \ar[d]_{\pi_2} & \> D_1 \ar[d]^{f} \\
D_2 \ar[r]_{g} & \> D_3
}
\]
and the following {\it universal mapping property of
fibred products\/} holds:
for any DFA $M$ and any two DFA $F^{-1}$-maps
$\mapdef{f'}{M}{D_1}$ and $\mapdef{g'}{M}{D_2}$
such that
\[f\circ f' = g\circ g',\]
as in the diagram below
%\[
%\matrice{
%M            &  \maprightu{f'}  &  D_1          \cr
%\mapdownl{g'}   &                 & \mapdownr{f}\cr
%D_2            & \maprightd{g}&  D_3,            \cr
%}
%\]
%
\[
\xymatrix{
M \ar[r]^{f'} \ar[d]_{g'} & \> D_1 \ar[d]^{f} \\
D_2 \ar[r]_{g} & \> D_3
}
\]
there is a
{\it unique\/} DFA $F^{-1}$-map $\mapdef{h}{M}{D}$ such that
\[f' = \pi_1\circ h
\quad\hbox{and}\quad
g' = \pi_2\circ h.\]
Prove that $D$ is unique up to a DFA $F^{-1}$-map isomorphism.
This means that if $D'$ is another DFA and if there are
two DFA $F^{-1}$-maps  $\mapdef{\pi_1'}{D'}{D_1}$
and $\mapdef{\pi_2'}{D'}{D_2}$ such that
\[f\circ \pi_1' = g\circ \pi_2'\]
and the universal mapping property of
fibred products holds, then
there are two unique DFA $F^{-1}$-maps $\mapdef{\varphi}{D}{D'}$ and
$\mapdef{\varphi'}{D'}{D}$ so that
$\varphi'\circ \varphi = \id_{D}$
$\pi_1 = \pi_1'\circ  \varphi$, $\pi_2 =  \pi_2'\circ \varphi$,
$\varphi\circ \varphi' = \id_{D'}$,
$\pi_1' = \pi_1\circ  \varphi'$ and $\pi_2' =  \pi_2\circ \varphi'$.


\remark
We denote $D$ by $D_1\prod_{D_3} D_2$ and call it
a {\it fibred product of $D_1$ and $D_2$ over $D_3$\/},
or a {\it pullback of $D_1$ and $D_2$ over $D_3$\/}.

\medskip
Letting $T$ denote any one-state DFA accepting $\emptyset$
(this single state is rejecting), observe that there is a unique
DFA $F^{-1}$-map from every DFA $D$ to $T$.
Use this to show that if $D_1\prod D_2$ is the
product DFA arising in (a), then
\[D_1\prod D_2 = D_1\prod_{T} D_2.\]


\vspace{0.25cm}\noindent
{\bf Extra Credit (40 points).}
Redo questions (a) and (b) for $F$-maps instead of
$F^{-1}$-maps.

\remark
If we dualize (b), i.e.,
turn the arrows around, we get the notion of
{\it fibred coproduct\/} or {\it pushout\/}.
It can be shown that fibred coproducts exist,
both for $F$-maps and $F^{-1}$-maps,
but this is  tricky.

\vspace{0.25cm} \noindent
\noindent
{\bf Solution B6}

\vspace{0.25cm}
\noindent
(a)(i) Proof:
Let $D_1 = (Q_1,\Sigma,\delta_1,q_{01},F_1)$, $D_2 = (Q_2,\Sigma,\delta_2,q_{02},F_2)$, and $D = (Q_D,\Sigma,\delta_D,q_{0D},F_D)$.
Construct $D, \pi_1, \pi_2$, as follows:
\begin{itemize}
	\item $Q_D = Q_1 \times Q_1$, $q_{0D}=(q_{01},q_{02})$, $F_D=\{(q_1,q_2)\ |\ \exists q_1 \in F_1 \ or \ \exists q_2 \in F_2\}$, $\delta_D((q_1,q_2),a)=(\delta_1(q_1,a),\delta_2(q_2,a))$.
	\item $\forall (q_1,q_2) \in D$, $\pi_1((q_1,q_2)) = q_1$, $\pi_2((q_1,q_2)) = q_2$.
\end{itemize}

As we can see
\begin{itemize}
	\item  $\pi_1(q_{0D}) = q_{01}$, $\pi_2(q_{0D}) = q_{02}$, and for any $q_D=(q_1,q_2) \in Q_D$, $\pi_1( \delta_D(q_D,a) )= \pi_1( ( \delta_1(q_1,a) , \delta_2(q_1,a) ) ) = \delta_1(q_1,a) = \delta_1( \pi_1( q_D), a ) $.
	\item For all string $w$ belonging to the language of $D_1$, $\delta^*_1(q_{01},w)=q_{1F} \in F_1$, $\delta^*_D(q_{0D}, w)=(q_{1F}, q_2) \in F_D$.
\end{itemize}
Then we have $\pi_1$ is a $F^{-1}$ map. Similarly, $\pi_2$ is also a $F^{-1}$ map.

\medskip
For any given DFA $M= (Q_M,\Sigma,\delta_M,q_{0M},F_M)$ and any two DFA $F^{-1}$-maps $\mapdef{f}{M}{D_1}$ and $\mapdef{g}{M}{D_2}$, assume $q_M \in Q_M$, $f(q_M)=q_1 \in Q_1$, and $g(q_M)=q_2 \in Q_2$, then we define $\mapdef{h}{M}{D}$, $h(q_M) = (q_1,q_2) \in Q_D$.

As we can see
\begin{itemize}
	\item  $h(q_{0M}) = (q_{01},q_{02}) = q_{0D}$, and for any $q_{M1} \in Q_M$, assume $\delta_M(q_{M1},a) = q_{M2}$, $h( q_{M1} ) = (q_{11},q_{21})$, $h( q_{M2} ) = (q_{12},q_{22})$. Since, $f$ and $g$ are morphism, then we have $\delta_1(q_{11},a) = q_{12}$, $\delta_2(q_{21},a) = q_{22}$. Then $ h( \delta_M( q_{M1} , a) )= h( q_{M2} ) = (q_{12},q_{22}) = \delta_M( h(q_{M2}) , a ) $.
	
	\item For ll string $w$ belonging to the language of $D_1$, $\delta^*_1(q_{01},w)=q_{1F} \in F_1$, $\delta^*_D(q_{0D}, w)=(q_{1F}, q_2) \in F_D$.
\end{itemize}
Then we have $h$ is a $F^{-1}$ map.

Supposing there is another $F^{-1}$ map $h'$, $ \forall q_M \in Q_M$, $f(q_M)=q_1 \in Q_1$, $g(q_M)=q_2 \in Q_2$. According to our construction of $\pi_1$, $\pi_2$, we must have $h'(q_M)=(q_1,q_2)$. That is to say, $h$ is unique.

\vspace{0.25cm}
\noindent
(a)(ii) Proof:
From the construction of $\pi_1$, $\pi_2$, it is trivial to prove that they are surjective.
Assume DFA $D'$ is another DFA which holds the property, then there is a $F^{-1}$ map $\mapdef{\varphi'}{D'}{D}$. We also know that $D$ hold the property, then there is a $F^{-1}$ map $\mapdef{\varphi}{D}{D'}$. According to the definition, $D$ is unique up to a DFA $F^{-1}$-map isomorphism.
The language accepted by $D$ is the union of the language of $D_1$ and the language of $D_2$.


\vspace{0.25cm}
\noindent
(b)(i) Proof:
Let $D_1 = (Q_1,\Sigma,\delta_1,q_{01},F_1)$, $D_2 = (Q_2,\Sigma,\delta_2,q_{02},F_2)$, $D_3 = (Q_3,\Sigma,\delta_3,q_{03},F_3)$, and $D = (Q_D,\Sigma,\delta_D,q_{0D},F_D)$.
Let $Q_{D'}= \{(q_1,q_2)\ | \ (\exists q_3 \in Q_3, f(q_1)=q(q_2)=q_3) \}$, construct $D, \pi_1, \pi_2$, as follows:
\begin{itemize}

\item $ Q_D = \{ (q_1,q_2) |  (\exists (q_1,q_2) \in Q_{D'} ) \& ( \forall a \in \Sigma  , ( \delta_1 ( f (q_1),a ) , \delta_2 (g(q_2),a) ) \in Q_{D'}) \}$, $q_{0D}=(q_{01},q_{02})$, $F_D=\{(q_1,q_2)\ |\ \exists q_1 \in F_1 \ or \ \exists q_2 \in F_2\}$, $\delta_D((q_1,q_2),a)=(\delta_1(q_1,a),\delta_2(q_2,a))$.

\item $\forall (q_1,q_2) \in D$, $\pi_1((q_1,q_2)) = q_1$, $\pi_2((q_1,q_2)) = q_2$.

\end{itemize}

As we can see
\begin{itemize}
	\item  $\pi_1(q_{0D}) = q_{01}$, $\pi_2(q_{0D}) = q_{02}$, and for any $q_D=(q_1,q_2) \in Q_D$, $\pi_1( \delta_D(q_D,a) )= \pi_1( ( \delta_1(q_1,a) , \delta_2(q_1,a) ) ) = \delta_1(q_1,a) = \delta_1( \pi_1( q_D), a ) $.
	\item For all string $w$ belonging to the language of $D_1$, $\delta^*_1(q_{01},w)=q_{1F} \in F_1$, $\delta^*_D(q_{0D}, w)=(q_{1F}, q_2) \in F_D$.
\end{itemize}
Then we have $\pi_1$ is a $F^{-1}$ map. Similarly, $\pi_2$ is also a $F^{-1}$ map.

\medskip
For any given DFA $M= (Q_M,\Sigma,\delta_M,q_{0M},F_M)$ and any two DFA $F^{-1}$-maps $\mapdef{f}{M}{D_1}$ and $\mapdef{g}{M}{D_2}$, assume $q_M \in Q_M$, $f(q_M)=q_1 \in Q_1$, and $g(q_M)=q_2 \in Q_2$, then we define $\mapdef{h}{M}{D}$, $h(q_M) = (q_1,q_2)$ $(q_1,q_2)$ must belongs to  $Q_D$, else it contradict with the fact that $f\circ f' = g\circ g'$.

As we can see
\begin{itemize}
	\item  $h(q_{0M}) = (q_{01},q_{02}) = q_{0D}$, and for any $q_{M1} \in Q_M$, assume $\delta_M(q_{M1},a) = q_{M2}$, $h( q_{M1} ) = (q_{11},q_{21})$, $h( q_{M2} ) = (q_{12},q_{22})$. Since, $f$ and $g$ are morphism, then we have $\delta_1(q_{11},a) = q_{12}$, $\delta_2(q_{21},a) = q_{22}$. Then $ h( \delta_M( q_{M1} , a) )= h( q_{M2} ) = (q_{12},q_{22}) = \delta_M( h(q_{M2}) , a ) $.
	
	\item For ll string $w$ belonging to the language of $D_1$, $\delta^*_1(q_{01},w)=q_{1F} \in F_1$, $\delta^*_D(q_{0D}, w)=(q_{1F}, q_2) \in F_D$.
\end{itemize}
Then we have $h$ is a $F^{-1}$ map.

Supposing there is another $F^{-1}$ map $h'$, $ \forall q_M \in Q_M$, $f(q_M)=q_1 \in Q_1$, $g(q_M)=q_2 \in Q_2$. According to our construction of $\pi_1$, $\pi_2$, we must have $h'(q_M)=(q_1,q_2)$. That is to say, $h$ is unique.

\vspace{0.25cm}
\noindent
(b)(ii) Proof:
From the construction of $\pi_1$, $\pi_2$, it is trivial to prove that they are surjective.
Assume DFA $D'$ is another DFA which holds the property, then there is a $F^{-1}$ map $\mapdef{\varphi'}{D'}{D}$. We also know that $D$ hold the property, then there is a $F^{-1}$ map $\mapdef{\varphi}{D}{D'}$. According to the definition, $D$ is unique up to a DFA $F^{-1}$-map isomorphism.
The language accepted by $D$ is the union of the language of $D_1$ and the language of $D_2$.


\vspace{0.25cm}
\noindent
(b)(iii) Proof:
For the construction of $D$, $D'$, $\pi_1$, $\pi_2$, it is easy to see that when $D_3=T$, $D$ and $D'$ are identical.

\vspace{0.5cm}\noindent{\bf TOTAL: 220 + 40 points.}

\end{document}

